# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/3 8:52 
"""
"""
模式匹配_BF算法
从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串的第二个字符开始和
模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S
中字符全部比较完，则说明比较失败
"""


def string_BF(lead_string, sub_string):
    """
    模式匹配
    Args:
        lead_string: 主串
        sub_string: 模式串

    Returns:d

    """
    print(len(lead_s1), len(sub_string))
    i, j = 0, 0
    while i < len(lead_string) and j < len(sub_string):
        if lead_string[i] == sub_string[j]:
            i += 1
            j += 1
        else:
            i -= (j - 1)
            j = 0
            print(lead_string[i], sub_string[j], i + 1, j + 1)
    return True if j == len(sub_string) else False


"""
性能分析：
设串S的长度为n,串T的长度为m,在匹配成功的情况下，考虑两种极端的情况：
情况1：最好的情况，即不成功匹配发生在T的第1个字符
设匹配成功发生在Si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的
匹配共比较了m次，所以共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，
则时间复杂度为O(n+m)


时间性能低的原因：
在每趟不成功时存在大量回溯，没有利用已经匹配到的结果

如何在匹配不成功时不回溯？
主串不回溯，模式就需要向右滑动一段距离
"""

"""
模式匹配：KMP（Knuth Morris Pratt）算法
定义next[j]函数，表征模式P种最大相同首子串和尾子串(真子串)的长度

表明当模式中第j个字符与主串中相应字符‘失配’时，在模式中需重新和主串中该字符
及逆行比较的字符的位置
k=next[j]
j=1,不比较，next[j]==0
p1...pk-1=P(j-(k-1))...pj-1, next[j]=max{k}
其他情况，next[j]=1

分析结论：主串中的i可以不回溯，模式向右华东到的新比较起点k，并且k仅与模式串P(模式串)有关！

如何由当前部分匹配结果确定模式向右华东的新比较起点k?
    计算next[j]的方法：
    - j==1，next[j]==0,表示根本不进行字符比较
    - j>1，next[j]的值为：
        模式串的位置从1到j-1构成的串所出现的首位相同的子串的最大长度+1
    - 当无首尾相同的子串next[j]的值为1
        next[j]=1表示从模式串头部进行字符比较


KMP思想：
    设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，
    把子串t称为模式串，因此定位也成为模式匹配。
    
算法流程：
    step1:在串S和串T中分别设比较的起始下标i和j;
    step2：循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
        if S[i]==T[j],继续比较S和T的下一个字符；否则
        将j向右滑动到next[j]的位置，即j=next[j]
        if j==0,则i和j分别加1,准备下一趟比较
    step3:如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0

"""


def get_next_j(s, j):
    if j == 1:
        return 0
    else:
        tmp_s = s[:j - 1]
        k = 0
        i=1
        while i < j-1:
            # print(f"tmp_s={tmp_s},tmp_s[:k]={tmp_s[:i]},tmp_s[j - k:]={tmp_s[j-i-1:]}")
            if tmp_s[:i] == tmp_s[j - i-1:]:
                k=len(tmp_s[:i]) if len(tmp_s[:i])>k else k
            i+=1
        return k+1


s = 'abaabcac'
for i in [1, 2, 3, 4, 5, 6, 7, 8]:
    # print(f"i={i}")
    k = get_next_j(s, i)
    # print(f"i={i},k={k}")



def string_KMP(lead_str, T_str):
    """
    基于KMP算法实现模式匹配
    Args:
        lead_str: 主串
        T_str: 模式串

    Returns:
        True if success else False

    """
    i, j = 0, 0
    while len(lead_str[i:]) > len(T_str) or j < len(T_str):
        print(i, j)
        if lead_str[i] == T_str[j]:
            i += 1
            j += 1
        else:
            # 子串
            j=get_next_j(T_str,j)
            if j==0:
                i+=1
                j+=1
    return True if j==len(T_str) else False


if __name__ == "__main__":
    lead_s1 = 'abacaba'  # 'aaaaaaaaaabccccc'#'ababcabcacbab'
    T_s = 'abab'  # "aaab"#'abcac'
    # print(string_BF(lead_s1, T_s))
    print(string_KMP(lead_s1, T_s))